The A* (Astar) algorithm is a form of heuristic search, where the heuristic is guaranteed to be a lower bound of the final cost of any solution beyond. It is particularly useful where the path taken to a solution is a major component of the final cost, and in spatial routing algorithms where Euclidean distance (as the crow flies) is a lower bound. The A* algorithm is a variant of best first search, but when a solutoon as been found, the fact that the heuristic is a lower bound means that all potential paths where the heuritsic is graeter than the cost of the current best soluton can be pruned.
Used on page 343
Using the A*algorithm